1. Field of the Invention
The present invention relates to an automatic element placement system in LSI design and, more particularly, to an element placement method and apparatus in which the positional relationship between elements on a circuit diagram are retained.
2. Description of the Related Art
In LSI design, it is important to place all the elements on a circuit diagram (schematic diagram) within a region having a small area while retaining the positional relationship between the elements to a certain extent. A conventional manual placement scheme can realize such high-density placement but demands skills and a long operation time.
Under the circumstances, automatic element placement apparatuses have been vigorously studied and developed to realize optimal or near-optimal element placement within a short period of time. For example, a procedure of automatic placement is disclosed in Sasaki and Susa, "Element Allocation Method in Generation of Analog Cells", Technical Study Report of the Institute of Electronics and Communication Engineers, VLD90-94, 1990. Many other methods using a genetic algorithm have been proposed.
Genetic algorithm have been proposed as stochastic optimization method s and general purpose search strategies, whose basic concept is based on organic solution processes such as natural selection and recombination mechanisms. A typical genetic algorithm starts with an initial population of solutions, and uses genetic operations such as selection, crossover and mutation to improve upon them.
In such an automatic placement system, however, element placement in an LSI is difficult to optimize (or near-optimize) by performing processing in consideration of the overall circuit arrangement, because an enormous number of elements, e.g., several thousands to several ten thousands' elements, are included in the circuit. Therefore, in a conventional method, an overall circuit is divided into small partial circuits as placement targets, and placement processing is performed in units of partial circuits. In this method, for example, an overall circuit is divided into small partial circuits as placement targets, and placement processing is sequentially performed, in units of partial circuits, from the left or right of the circuit diagram. Although the manner of dividing an overall circuit into partial circuits as placement targets greatly influences a final circuit placement result, a dividing method has not completely established yet, and such a dividing operation is performed by trial and error or an empirically obtained rule. In the case that the circuit diagram is constituted by small partial circuits each having a specific function, a dividing method is established. In addition, there are no satisfactory solutions as to how placement results corresponding to the respective partial circuits as placement targets obtained by a dividing operation are connected to each other efficiently to improve the performance of a placement result corresponding to the overall circuit.
That is, an element placement result provided by a conventional automatic placement system is on a lower level as the (near-) optimal solution, which is not satisfactory as compared with a conventional manual design scheme. There are methods by which a result almost equivalent to that obtained by manual design in terms of integration density can be finally obtained. Such methods, however, are not perfectly automated and require trial-and-error operations, taking a long processing time to obtain a solution.
Sasaki et al. introduce evaluation values associated with constraints such as neighbourhood-relation of elements (the evaluation values of an element placement result will be referred to as "costs" hereinafter) and several types of evaluation functions (to be referred to as "cost functions" hereinafter) for defining a cost associated with the region area occupied by all elements, a cost associated with the overall length of nets among elements, and the like, and they disclose a placement algorithm based on a simulated annealing method to minimize each cost as far as possible. In this case, Sasaki et al. adopt a method of multiplying the cost functions by weighting coefficients corresponding to the significance levels of the respective cost functions, and using the sum of modified the cost functions to evaluate each placement result.
According to Sasaki et al., although the respective cost functions can be ordered in accordance with their significance levels, no method and criterion for quantizing each significance level as a weighting coefficient are disclosed, and such coefficients are empirically set/modified.
Furthermore, in placement algorithms based on genetic algorithms, similar methods have been adopted.
As described above, in the conventional LSI element placement methods, the optimal or near-optimal placement results with respect to all types of cost functions associated with various constraints cannot be obtained.
As a criterion for evaluating the quality of placement result, the degree to which elements are lined up along the x-direction (i.e., horizontally) is checked. This is because alignment of elements in the horizontal direction facilitates wiring and requires only a small unused area. However, no practical method of aligning elements in the lateral direction to a possible extent has been disclosed.
As described above, in the conventional LSI element placement methods, various problems are posed in obtaining a high-quality placement result.